1. Field of the Invention
The invention relates to a method for routing nets within an integrated circuit (IC) layout by iteratively partitioning the layout into progressively smaller tiles, routing each net crossing a tile boundary after each partitioning without altering any previously routed net, then iteratively partitioning the layout into progressively larger tiles, routing each previously unrouted net crossing a tile boundary after each partitioning, altering existing net routes when necessary.
2. Description of Related Art
IC fabricators provide cell libraries describing a set of standard cells that an IC designer can incorporate into an IC design. Each standard cell is an IC component of proven design such as, for example, a transistor, a logic gate, an input/output port, or a more complicated device such as a memory. An IC designer typically develops an IC design in the form of a “netlist”, a data file describing the IC as a collection of instances of cells and indicating which terminals of the cells are to be interconnected by signal paths (“nets”). The IC designer employs a computer-aided placement and routing tool employing placement algorithm that processes the netlist to produce a placement plan indicating a position of each cell instance within the IC and a routing algorithm to produce a routing plan indicating a route for each net interconnecting cells instances. Placement and routing is typically an iterative process; if the routing algorithm fails to find a route for each net, the placement algorithm modifies the placement plan and the routing algorithm and again attempts to find a route for each net. An efficient routing algorithm that is more likely to find a route for each net when possible for a given placement plan, and which does so quickly, can greatly reduce the processing time needed for placement and routing.
FIG. 1 illustrates a simple routing algorithm that divides the IC layout area into an array of rectangular tiles 30 (step 10) as shown in FIG. 2A. A router implementing the routing algorithm then processes the netlist to define a set of connections for each net (step 12). A “connection” is a signal path between two cell terminals. For example, a net connecting only two cell terminals consists of a single connection while a net connecting four cell terminals consists of three connections. FIG. 2A shows an unrouted net 31 consisting of two connections 31A and 31B connecting terminals of three cells 32, 33 and 34. After defining all connections (step 12), the router selects one of the unrouted nets (step 14) and a first connection of that net (step 16), and then determines a global route for that connection (step 18). For example FIG. 2B shows that with net 31 selected at step 14 and connection 31A selected at step 16, a global route is selected for connection 31A. A “global route” for a connection is simply a list of the particular tiles through which the net is to pass that does not indicate the exact (“detailed”) route of the connection through any individual tile. The router will typically look for a route that minimizes a routing cost function related to the density of connections crossing the individual tile boundaries. The routing cost function is designed so that routing a connection in a way that minimizes the cost function and increases the likelihood that the router will be able to successfully route all nets that have not yet been routed. After selecting the global route for a connection at step 18, the router establishes a detailed route for the connection defining the structures on each layer of the IC within each tile included in the global route (step 20). For example, FIG. 2C shows a detailed route for connection 34.
When there is a next connection of the selected net to be routed (step 22), the router selects the next connection (step 16) and then globally routes the next connection (step 18). FIG. 2D shows a global route for connection 31B of net 31 of FIG. 2A. At step 20, the router then tentatively establishes a detailed route for the connection and then refines the detailed routing to eliminate any redundancy. For example after establishing a tentative detailed route for connection 34B as illustrated in FIG. 2E, the algorithm refines the routing of connections 34A and 34B as shown in FIG. 2F by eliminating redundant routing in three of the tiles so that the follow the same path 34C where possible, thereby reducing congestion within the tiles and at tile boundaries. The router continues to repeat steps 16-20 until all connections of the selected net have been routed. When there is a next net to be routed (step 24) the algorithm selects the next net and repeats steps 14-22 to route all of its connections. The process continues until at step 24 the router has routed all nets.
As the number of nets the algorithm has routed increases, the available routing space decreases, and the algorithm of FIG. 1 becomes less likely to successfully route additional nets. To increase the likelihood of success, a prior art, multi-level “Λ-shaped”, routing framework as illustrated in FIG. 3 carries out routing in several stages. The IC's floorspace is initially divided into an array 40A of relatively small tiles and a router separately routes each tile of the array 40A to find a detailed route for each net that resides completely within that tile. Nets crossing boundaries of tiles 42 are ignored and remain unrouted. At a next stage of the process the IC tiling is coarsened so that each set of four tiles 42 of array 40A are merged to create a single larger tile 44 of a tile array 40B. The router repeats the routing algorithm of FIG. 1 for each tile 44 but only the unrouted nets residing wholly within any individual tile 44 are routed; unrouted nets crossing boundaries of tiles 44 are ignored. Thus for each tile 44, connections for the unrouted nets residing wholly within that tile 44 are identified (step 12), and each such connection of each net is globally routed and detailed routed with respect to smaller tiles 42 (steps 14-24). When the algorithm is unable to route a net residing wholly within any given tile 44, it simply notes that it failed to route that net, and continues to route additional nets. At the next stage of the process, IC tiling is again coarsened so that each set of four tiles 44 of array 40B are merged to create a single larger tile 46 of a tile array 40C. In this simple example, the algorithm reaches the coarsest (single tile) stage in only two coarsening steps, but an IC layout may initially be divided into more tiles requiring more coarsening stages to reach the coarsest, single tile stage. The router then repeats the routing algorithm of FIG. 1 for tile 46 to determine a global and then a detailed route for each net crossing a boundary of a tile 44.
At this point, the algorithm will have attempted to route every net and will likely have succeeded in routing most of them. The algorithm then begins a series of uncoarsening stages. During the first uncoarsening stage, the algorithm divides the IC into an array 40D of four tiles 47 and finds a route for local nets within any tile 47, rerouting previously routed nets within that tile when necessary to provide a path for the net being routed. The algorithm then again un-coarsens the tiling to produce a new tile array 40E wherein each tile 47 of array 40D is divided into four smaller tiles 48. The algorithm then finds a route for each unrouted local net residing wholly within any tile 48, rerouting other local nets wholly within the tile as necessary to eliminate excessive congestion at tile boundaries. The routing process ends after the algorithm has reached the finest tiling level and has routed all nets.
The path delay through a net increases with its length, and nets can form signal paths that may be subject to restrictions on path delays. It is therefore helpful to route nets interconnecting widely spaced cells in as direct a manner as possible in order to limit the nets' contributions to signal path. Since the prior art Λ-shaped framework of FIG. 3 first routes shorter nets without considering the routing resource requirements of later routed longer nets, wrong routing choices with respect to short, local nets during the early stages of the process make routing of the more timing critical longer nets more difficult and can complicate and lengthen the refinement process carried out during the later stages of the process.
Prior art “grid-based” routing algorithms that route nets along pre-established grid lines treat all wires as having the same width and required spacing between wires. However grid-based routing algorithms are not suitable for routing modern ICs, where nanometer-scale optical fringing and other effects can influence net width and spacing, particularly since optical proximity correction (OPC) and phase-shift mask (PSM) procedures have been developed to adjust width and spacing of individual wires to correct for these influences. “Gridless” routing systems are preferable because they do not restrict wire routing to pre-established grid lines and can accommodate variations in wire width and spacing.
What is needed is a gridless routing algorithm that gives priority to routing longer signal paths but which, when routing any net, takes into account estimated routing resource requirements of all unrouted nets to minimize the impact on the routing resources that will be required by the later routed nets.